COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00011 00003	
C00012 00004	.skip 2
C00013 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.turn off "{"
.CB PATTERN DIRECTED COMPUTATION AND PROBLEM SOLVING


	This is a preliminary report on an investigation that has
changed its character as it proceeded.  Since I am not sure where
it will finish, I'll start with the problem as originally posed
and show how several stages of generalization have led to its
present state.

	We begin with what we call %2syntax-directed computation%1
which we will generalize to %2pattern-directed computation%1
although syntactic patterns will remain an important case.
The term %2syntax-directed computation%1 is itself a generalization
of %2syntax-directed compiling%1 and %2syntax-directed input-output%1.

	The idea of syntax-directed computation is quite simple and
quite old.  It is quite tempting, for example, to try to describe
differentiation and algebraic simplification with a collection of rules like

	%2D(u + v) → Du + Dv%1

and

	%2u + 0 → u%1.

We will work in the framework of LISP, for reasons that will become
apparent and which are not merely parochial, so the above transformations
become

	(DIFF (PLUS U V)) → (PLUS (DIFF U) (DIFF V))

and

	(PLUS U 0) → U.

At first sight it seems more pleasant to write such rules than
to write programs in LISP or any other programming language, and
so many special languages and packages within languages like LISP have
been written that interpret collections of transformation rules or
compile them into program.

	One immediate question is whether there is any limit on what can
be done by transformation rules or whether any computable function of
symbolic expressions can be computed by such a system.  The answer has
been known since the 1930s; any computable function can be computed by a
Post canonical system which is one system for writing such rules.
However, the proof involves using such rules to simulate a universal
Turing machine or a computer or to make a set of rules constituting an
interpreter for some programming language.  The state of 
the computation is represented by a symbolic expression with
special symbols to mark the current instruction.  The syntax rules
must therefore move the special symbol to search for the next
instruction.

	It is therefore entirely clear that
there is no programming or practical advantage in writing syntax
transformation rules to simulate a program.  Therefore, the question of
what computations are conveniently done by sets of syntax transformation
rules remains.  The practical systems all allow the admixture of
conventional computation in one way or another, and programmers in these
languages make frequent though often obscure use of these facilities.

	These practical languages include COMIT (early but defunct),
SNOBOL (widely used, but rarely for heavy computation) and various
packages in LISP such as METEOR (early but defunct) and 
also some of the features of Micro-planner and QLISP.

	Our first idea is that instantiation is a special case of pattern
recognition which is a special case of problem solving.  We start
with the LISP function ⊗inst which does a simple form of instantiation
and generalize it in stages to a problem solver for a certain class
of ⊗obvious problems.  In the present draft, it is not yet clear what
our notion of ⊗obvious shall be.

	We begin with
.begin nofill

	%2inst[pat,expr,a] ←
		qif a qeq %1NO%2 qthen %1NO%2
		qelse qif isvar pat
			qthen {assoc[pat,a]}[λz.
				qif qn z qthen [pat.expr].a
				qelse qif qd z qeq expr qthen a
				qelse %1NO%2]
		qelse qif qat pat qthen [qif pat qeq expr qthen a qelse %1NO%2]
		qelse qif qat expr qthen %1NO%2
		qelse inst[qd pat,qd expr,inst[qa pat,qa expr,a]]]%1.
.end

	Here ⊗pat is a pattern such as (PLUS X Y) where we suppose that
the predicate ⊗isvar knows that X and Y are variables and PLUS 
is not.  ⊗expr is an expression, for example (PLUS (TIMES A B) C),
and ⊗a is an a-list, i.e. a list of dotted pairs, each of which is
a variable paired with a value.  ⊗inst is usually called with %2a_=_NIL%1,
and we have

	%2inst[%1(PLUS_X_Y),(PLUS_(TIMES_A_B)_C),NIL]_=_((X . (TIMES A B))(Y . C)).

In general, however, ⊗a gives the commitments for the variables that have
already been made, and this is used in the recursion.
The value of ⊗inst[pat,expr,a] is the a-list of commitments required to make
the pattern ⊗pat match the expression ⊗expr.  ⊗inst is the inverse of the
function ⊗sublis defined by

	%2sublis[a,pat] ←
		qif isvar pat qthen qd assoc[pat,a]
		qelse sublis[a,qa pat].sublis[a,qd pat]%1.

in the sense that

	%2inst[pat,expr,a] ≠ %1NO%2 ⊃ sublis[inst[pat,expr,a],pat] = expr%1.

	When we try to use ⊗inst for algebraic computation, we immediately
encounter the fact that many interesting operations such as addition
are commutative, and our pattern recognition needs to take this into
account.  Thus if we want a rule %2cos%52%2x_+_sin%52%2x_→_1%1, and
we want it to recognize %2cose%52%2x%1 and %2sin%52%2x%1 anywhere
in a sum, we can't do it with ⊗inst.  We can patch up ⊗inst to allow
this by introducing the following term into its definition:


Notes:

	Bound variables raise two kinds of problem for pattern
recognition.  First, a free occurence of an expression in
a quantified or lambda-ized context should be treated correctly.
Second, and ultimately more important, λ-abstraction is an important
form of pattern recognition.  Thus we would like to recognize
%2(a_+_b)%52%2_a_+_b%1 as an instance of %2f(a_+_b)%1.
It seems that recognition of such patterns is both extremely
powerful in that it may contain a substantial part of the AI
problem and, consequently, extremely difficult.
.skip 2
.begin verbatim
John McCarthy
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305

ARPANET: MCCARTHY@SU-AI
.end

.turn on "{"
%7This draft of PATTER[F76,JMC] PUBbed at {time} on {date}.%1